1. Field of the Invention
The present invention relates to a sorter for sorting data based on a plurality of reference value data.
2. Description of the Related Art
An image processor synthesizes and outputs various kinds of image signals for a CRT display based on image information transmitted from the exterior of the image processor. The image processor can synthesize and output a three-dimensional image as well as a two-dimensional plane image. Accordingly, for example, the image processor is widely used for a video game for the three-dimensional image, computer graphics, a display arranged in a device for CAD, and other devices.
When a deep three-dimensional image is synthesized in real time by using the image processor, it is necessary to sort three-dimensional data of each of processed images with respect to a processed polygon for 1/60 second at a high speed on the basis of image data on a Z-axis constituting coordinate values in a deep direction of each of the images.
Therefore, it is desirable to provide a sorter for sorting a plurality of three-dimensional image data at a high speed on the basis of predetermined data on the Z-axis.
However, in a general sorter, adjacent data on the Z-axis included in each of the image data are sequentially compared with each other and are rearranged with respect to all the image data.
In such processing, all Z-axis data between memories must be repeatedly transferred many times. Accordingly, it is impossible to perform a sorting operation of the image data at a high speed.
In particular, in such a general sorter, much time and labor are required in the sorting operation when the number of Z-axis data to be compared is increased. Accordingly, when the sorting operation is performed at a high speed, it is necessary to use a relatively large-sized computer so that the entire sorter is complicated in structure and is increased in cost.
Japanese Patent Application Laying Open (KOKAI) No. 2-224018 (international patent class G06F 7/24) shows a sorter for sorting a plurality of image data at a high speed by a simplified structure. In this sorter, the sorting operation can be performed at a high speed even when the number of image data on a reference axis as sorted data is large.
This sorter inputs the reference axis data as sorted data to a first buffer memory and a last buffer memory in a data number order.
The first buffer memory stores a data number to a memory area for a first data number when corresponding reference axis data are first inputted to the first buffer memory.
Similarly, the last buffer memory sequentially updates and stores this data number to a memory area for a last data number every time the corresponding reference axis data are read. Accordingly, the data number provided at a final reading time of the corresponding reference axis data is stored to the memory area for a last data number.
When the data number stored to the memory area for a last data number is updated and stored to the last buffer memory, the data number previously stored to this memory area and a newly stored data number are inputted to a chain buffer memory.
The chain buffer memory writes the new updated data number to a memory area for a chain data number designated by the data number before update every time data in the memory area for a last data number are updated. Accordingly, when the reference axis data having the same value and different from each other only in data number are repeatedly inputted to the chain buffer memory, historical contents of these reference axis data are written to the memory area for a chain data number. These historical contents show a data number order of the inputted reference axis data.
After sequential data writing operations are completely performed with respect to the first buffer memory, the last buffer memory and the chain buffer memory, the data number stored to the memory area for a first data number having a predetermined relation corresponding to the last data number is sequentially written to the memory area for a chain data number designated by the data number stored to the memory area for the last data number. Thus, the data number is written to each of memory areas for chain data numbers such that the reference axis data are chained together in an ascending or descending order.
A sorting circuit reads the data number written to each of the memory regions for chain data numbers in accordance with a predetermined reading rule. Thus, the inputted reference axis data are outputted in a data number order.
Thus, the inputted reference axis data are sorted and outputted in the ascending or descending order.
The image processor performs a three-dimensional clipping operation for removing a polygon having small Z-axis data with respect to the screen and a polygon having large Z-axis data with respect to a boundary limit. The image processor also performs a three-dimensional clipping operation for removing a polygon located in an arbitrary Z-axis data region. The image processor further performs a three-dimensional picking operation for leaving only the polygon located in the arbitrary Z-axis data region.
However, in the above sorting system, after the entire sorting operation is performed, a certain limited Z-value is required to perform the three-dimensional clipping operation for removing a polygon having a small Z-value with respect to a screen face and a polygon having a large Z-value with respect to the limit of a visual field. This limited Z-value is also required to perform the three-dimensional picking operation for leaving only a polygon located in an arbitrary Z-axis region. Accordingly, plural image data are excessively transferred since these data are sorted on the basis of a predetermined reference axis.